package com.lfg.leetcode.leetcode0;

import java.util.Stack;

/**
 *
 */

public class No32LongestValidParentheses {


    public static int longestValidParentheses(String s) {
        if (null == s || "".equals(s)) {
            return 0;
        }
        int length = s.length();
        int maxIndex = length - 1;
        int[] ret = new int[length];
        for (int i = length - 1; i >= 0; i--) {
            Character c = s.charAt(i);
            if (c == ')') {
                continue;
            }
            if (c == '(' && i < maxIndex) {
                if (i + 1 >= length) {
                    continue;
                }
                if (s.charAt(i + 1) == ')') {
                    ret[i] = 2;
                    int index = i + ret[i];
                    if (index >= length) {
                        continue;
                    }
                    ret[i] += ret[index];
                } else {
                    int index = i + ret[i + 1] + 1;
                    if (index >= length) {
                        continue;
                    }
                    if (s.charAt(index) == ')') {
                        ret[i] += ret[i + 1] + 2;
                        index++;
                        if (index >= length) {
                            continue;
                        }
                        ret[i] += ret[index];
                    }

                }
            }
        }
        int cnt = 0;
        for (Integer aCount : ret) {
            cnt = Math.max(cnt, aCount);
        }
        return cnt;
    }

    public static int longestValidParentheses2(String s) {
        if (null == s || "".equals(s)) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int cnt = 0;
        int ret = 0;
        for (int i = 0; i < s.length(); i++) {
            Character c = s.charAt(i);
            if (c != '(' && c != ')') {
                cnt = 0;
                continue;
            }
            if (c == '(') {
                if (cnt > 0) {
                    stack.push(cnt);
                    cnt = 0;
                }
                stack.push(-1);
                continue;
            }
            Integer tmp = pop(stack);
            if (null == tmp) {
                if (cnt > 0) {
                    ret = Math.max(cnt, ret);
                    cnt = 0;
                }
                continue;
            }
            if (tmp == -1) {
                cnt += 2;
            }
            tmp = pop(stack);
            if (null == tmp) {
                continue;
            }
            if (tmp > -1) {
                cnt += tmp;
            } else {
                stack.push(tmp);
            }
        }
        ret = Math.max(cnt, ret);
        for (Integer aCount : stack) {
            ret = Math.max(ret, aCount);
        }
        return ret;
    }

    private static Integer pop(Stack<Integer> stack) {
        if (stack.size() > 0) {
            return stack.pop();
        }
        return null;
    }

    public static void main(String[] args) {
//        int ret = longestValidParentheses("()(())");
        int ret = longestValidParentheses("(((()(()");
        System.out.println(ret);
    }
}

